package myTree;

class ThNode                //线索二叉树结点类型
{
    char data;                //存放结点值
    ThNode lchild, rchild;        //左、右孩子或线索的指针
    int ltag, rtag;            //左、右标志

    public ThNode()            //默认构造方法
    {
        lchild = rchild = null;
        ltag = rtag = 0;
    }

    public ThNode(char d)        //重载构造方法
    {
        data = d;
        lchild = rchild = null;
        ltag = rtag = 0;
    }
}

public class ThreadTree {
    ThNode b;            //二叉树的根结点
    ThNode root;        //线索二叉树的头结点
    ThNode pre;            //用于中序线索化,指向中序前驱结点
    String bstr;

    public ThreadTree() {
        root = null;
    }

    //中序线索二叉树的基本运算
    public void createTh()    //建立以root为头结点的中序线索二叉树
    {
        root = new ThNode();        //创建头结点root
        root.ltag = 0;
        root.rtag = 1;    //头结点域置初值
        if (b == null)        //b为空树时
        {
            root.lchild = root;
            root.rchild = null;
        } else                //b不为空树时
        {
            root.lchild = b;
            pre = root;        //pre是p的前驱结点,用于线索化
            threading(b);        //中序遍历线索化二叉树
            pre.rchild = root;    //最后处理,加入指向根结点的线索
            pre.rtag = 1;
            root.rchild = pre;    //根结点右线索化
        }
    }

    private void threading(ThNode p)      //对以p为根结点的二叉树进行中序线索化
    {
        if (p != null) {
            threading(p.lchild);        //左子树线索化
            if (p.lchild == null)        //前驱线索
            {
                p.lchild = pre;        //给结点p添加前驱线索
                p.ltag = 1;
            } else p.ltag = 0;
            if (pre.rchild == null) {
                pre.rchild = p;        //给结点pre添加后继线索
                pre.rtag = 1;
            } else pre.rtag = 0;
            pre = p;                //置p为下一次访问结点的前驱结点
            threading(p.rchild);        //右子树线索化
        }
    }

    public void thInOrder()        //中序线索二叉树的中序遍历
    {
        ThNode p = root.lchild;        //p指向根结点
        while (p != root) {
            while (p != root && p.ltag == 0)    //找中序开始结点
                p = p.lchild;
            System.out.print(p.data + " ");    //访问p结点
            while (p.rtag == 1 && p.rchild != root) {
                p = p.rchild;            //如果是线索，一直找下去
                System.out.print(p.data + " "); //访问p结点
            }
            p = p.rchild;            //如果不再是线索，转向其右子树
        }
    }


}

